/**
 * Created with IntelliJ IDEA.
 * Description:
 * https://gitee.com/li--jiaqiang/java-test.git
 * git pull
 * git pull origin master
 * git pull origin master --allow-unrelated-histories
 * User: 86187
 * Date: 2022-04-28
 * Time: 19:00
 */

//Scanner scan = new Scanner(System.in);


class Node {
    public int data;
    public Node next;
    public int size = 0;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class MyLinkList2 {

    public int size = 0;
    public Node head; // 初始值是 null

    //头插法
    public void addFirst(int data) {
        Node newNode = new Node(data);

        if(this.head == null) {
            this.head = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
        size++;
    }
    //尾插法
    public void addLast(int data) {
        Node newNode = new Node(data);

        if(this.head == null) {
            this.head = newNode;
        } else {
            Node pos = this.head;
            while(pos.next != null) {
                pos = pos.next;
            }
            pos.next = newNode;
        }
        size++;
    }

    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data) {
        if(index < 0 || index > size) {
            throw new RuntimeException("index位置不合法！");
        }

        int count = 0;
        if(index == 0) {
            addFirst(data);
        } else if(size == index) {
            addLast(data);
        } else {
            Node pos = this.head;
            while(pos != null) {
                if(count == index-1) {
                    Node newNode = new Node(data);

                    Node newNext = pos.next;
                    pos.next = newNode;
                    newNode.next = newNext;
                }
                pos = pos.next;
                count++;
            }
        }
        return true; //插入成功返回true
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        Node pos = this.head;
        while(pos != null) {
            if(pos.data == key) {
                return true;
            }
            pos = pos.next;
        }
        return false;
    }

    //判断链表是否为空
    private boolean judge() {
        return (this.head == null);
    }

    //头删
    private void removeFirst() {
        Node pos = this.head;
        this.head = pos.next;
        size--;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if(judge()) {
            return;
        }
        if(this.head.data == key) { //头删
            removeFirst();
            return;
        }
        Node pos = this.head;
        Node tail = this.head;
        while(pos != null) {
            if(pos.data == key) {
                tail.next = pos.next;
                size--;
                return;
            }
            tail = pos;
            pos = pos.next;
        }
    }
    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if(judge()) {
            return;
        }

        while(this.head.data == key) { //头删
            removeFirst();
            if(judge()) { //删除后判断链表是否为空
                return;
            }
        }

        Node pos = this.head;
        Node tail = this.head;
        while(pos != null) {
            if(pos.data == key) {
                tail.next = pos.next;
                size--;
                pos = pos.next;
                continue;
            }
            tail = pos;
            pos = pos.next;
        }

    }

    //得到单链表的长度
    public int size() {
        return size;
    }

    //打印
    public void display() {
        Node pos = this.head;
        while(pos != null) {
            System.out.print(pos.data+" ");
            pos = pos.next;
        }
        System.out.println();
    }
    //销毁链表
    public void clear() {
        head = null;
    }

}
